1. Field of the Invention
The invention relates to wireless communication, and more particularly to a maximum likelihood detection (MLD) method and system, applying a sphere decoder to multiple-input multiple-output (MIMO) technology.
2. Description of the Related Art
MIMO is an abstract mathematical model for multi-antenna communication systems. MIMO technology has attracted the attention of wireless communications developers, because it significantly increases transmission throughput and range at the same bandwidth and same overall transmitting power. In general, MIMO technology increases the spectral efficiency of a wireless communication system. MIMO exploits the multipath scattering effect to increase data throughput and range, or reduce bit error rate, rather than attempting to eliminate it as in conventional SISO (Single-Input Single-Output) communication systems. MIMO can also be used in conjunction with Orthogonal Frequency Division Multiplexing (OFDM), and is now part of the IEEE 802.16 standard and will also be included in the IEEE 802.11n High-Throughput standard, which is expected to be finalized in mid 2007. Standardization of MIMO to be used in 3G standards such as High-Speed Downlink Packet Access (HSDPA) is currently ongoing. A typical MIMO data model is illustrated in FIG. 1.
A baseband equivalent data model in which a transmitter comprises Nt transmit antennas and a receiver comprises Nr receive antennas is represented as:{tilde over (y)}={tilde over (H)}{tilde over (s)}+ñ, 
  where  ,          ⁢            y      ~        =          [                                                  y              1                                                                          y              2                                                            ⋮                                                              y                              N                r                                                        ]        ,          ⁢            s      ~        =          [                                                  s              1                                                                          s              2                                                            ⋮                                                              s                              N                t                                                        ]        ,          ⁢            n      ~        =          [                                                  n              1                                                                          n              2                                                            ⋮                                                              n                              N                r                                                        ]        ,          ⁢            H      ~        =          [                                                  h              11                                                          h              12                                            ⋯                                              h                              1                ⁢                                  N                  t                                                                                                        h              21                                                          h              22                                            ⋯                                              h                              2                ⁢                                  N                  t                                                                                          ⋮                                ⋮                                ⋱                                ⋮                                                              h                                                N                  r                                ⁢                1                                                                        h                                                N                  r                                ⁢                2                                                          ⋯                                              h                                                N                  r                                ⁢                                  N                  t                                                                        ]        ,          ⁢      n    ~  represents the noise added to the receiver, {tilde over (H)} represents a channel transformation function, and hij represents the channel response from j-th transmit antenna to i-th receive antenna. Referring to the baseband data model, {tilde over (y)}, {tilde over (s)}, ñ, and {tilde over (H)} are complex vectors, which can be converted to a real data model, represented as:
                    [                                                            Re                ⁡                                  (                                      y                    ~                                    )                                                                                                        Im                ⁡                                  (                                      y                    ~                                    )                                                                    ]            ︸        y    =                                          [                                                                                Re                    ⁡                                          (                                              H                        ~                                            )                                                                                                            -                                          Im                      ⁡                                              (                                                  H                          ~                                                )                                                                                                                                                              Im                    ⁡                                          (                                              H                        ~                                            )                                                                                                            Re                    ⁡                                          (                                              H                        ~                                            )                                                                                            ]                    ︸                H            ⁢                                    [                                                                                Re                    ⁡                                          (                                              s                        ~                                            )                                                                                                                                        Im                    ⁡                                          (                                              s                        ~                                            )                                                                                            ]                    ︸                s              +                                        [                                                                                Re                    ⁡                                          (                                              n                        ~                                            )                                                                                                                                        Im                    ⁡                                          (                                              n                        ~                                            )                                                                                            ]                    ︸                n            .      
A MIMO receiver detects the transmitted symbols ‘s’ according to the received signals ‘y’.
Typically, maximum likelihood detection (MLD), with complexity proportional to 2Nt*Mc, where Nt is the number of transmit antennas and Mc is the modulation order, is considered the optimal signal detection method. If the transmitter, for example, comprises 4 antennas, indicating signal s comprises 4 symbols (s1˜s4) and each symbol is modulated according to 64-quadrature amplitude modulation (64-QAM, Mc=6), to obtain the optimal solution, the receiver must examine 644 possible solutions. Such a high-complexity method, however, may in practice be impossible to implement. Accordingly, sub-optimal detection methods with lower complexity are provided, such as Vertical Bell Laboratories Layered Space-Time (V-BLAST), Zero Forcing (ZF), and Minimum Mean Square Error (MMSE). Furthermore, a sphere decoding (SD) method is also provided to efficiently decrease the complexity of the MLD. Conventional ML detection methods introduce a cost function that considers Nt transmitted symbols jointly while the sphere decoding method, on the other hand, can take apart the joint cost function into partial functions such that signal combinations apparently exceeding predefined cost constraints can be reasonably eliminated. The MLD is mathematically described to be equivalently represented as:
                                                           s              ^                        ML                    =                    ⁢                      arg            ⁢                                                  ⁢                                          min                                  s                  ∈                  Λ                                            ⁢                                                                                      y                    -                    Hs                                                                    2                                                                                  =                    ⁢                      arg            ⁢                                                  ⁢                                          min                                  s                  ∈                  Λ                                            ⁢                              {                                                                                                    (                                                  s                          -                                                                                    s                              ^                                                        ZF                                                                          )                                            H                                        ⁢                                          H                      H                                        ⁢                                          H                      ⁡                                              (                                                  s                          -                                                                                    s                              ~                                                        ZF                                                                          )                                                                              +                                                                                    y                        H                                            ⁡                                              (                                                  I                          -                                                                                                                    H                                ⁡                                                                  (                                                                                                            H                                      H                                                                        ⁢                                    H                                                                    )                                                                                                                            -                                1                                                                                      ⁢                                                          H                              H                                                                                                      )                                                              ⁢                    y                                                  }                                                                                  =                    ⁢                      arg            ⁢                                                  ⁢                                          min                                  s                  ∈                  Λ                                            ⁢                              {                                                                            (                                              s                        -                                                                              s                            ~                                                    ZF                                                                    )                                        H                                    ⁢                                      H                    H                                    ⁢                                      H                    ⁡                                          (                                              s                        -                                                                              s                            ~                                                    ZF                                                                    )                                                                      }                                                                                  =                    ⁢                      arg            ⁢                                                  ⁢                                          min                                  s                  ∈                  Λ                                            ⁢                                                {                                                                                                                                      H                          ⁡                                                      (                                                          s                              -                                                                                                s                                  ~                                                                ZF                                                                                      )                                                                                                                      2                                        ≤                                          r                      2                                                        }                                .                                                        
The symbol ^ indicates a set of all symbol vectors ‘s’ and ∥H(s−{tilde over (s)}ZF)∥2 indicates a transformed cost function. The set of {Hs} is regarded as the lattice generated by H and ‘s’ can be regarded as the coordinates of the lattice point. The MLD method searches the lattice to locate a lattice point closest to H{tilde over (s)}ZF. Thus, H{tilde over (s)}ZF can be served as a sphere center, and an abstract spherical surface in multidimensional space can be created when an applicable radius ‘r’ is defined. The MLD method searches out the coordinate of a lattice point closest to the sphere center H{tilde over (s)}ZF, as shown in FIG. 2. The MLD equivalent function is further simplified and represented as:
                                                           s              ^                        ML                    =                    ⁢                      arg            ⁢                                                  ⁢                                          min                                  s                  ∈                  Λ                                            ⁢                                                                                      y                    -                    Hs                                                                    2                                                                                  =                    ⁢                      arg            ⁢                                                  ⁢                                          min                                  s                  ∈                  Λ                                            ⁢                              {                                                                            (                                              s                        -                                                                              s                            ~                                                    ZF                                                                    )                                        H                                    ⁢                                      H                    H                                    ⁢                                      H                    ⁡                                          (                                              s                        -                                                                              s                            ~                                                    ZF                                                                    )                                                                      }                                                                                  =                    ⁢                      arg            ⁢                                                  ⁢                                          min                                  s                  ∈                  Λ                                            ⁢                              {                                                                            (                                              s                        -                                                                              s                            ~                                                    ZF                                                                    )                                        H                                    ⁢                                      R                    H                                    ⁢                                      R                    ⁡                                          (                                              s                        -                                                                              s                            ~                                                    ZF                                                                    )                                                                      }                                                                                  =                    ⁢                      arg            ⁢                                                  ⁢                                          min                                  s                  ∈                  Λ                                            ⁢                                                                                                              R                      ⁡                                              (                                                  s                          -                                                                                    s                              ~                                                        ZF                                                                          )                                                                                                  2                                .                                                        
R indicates an upper triangular matrix and is generated by QR decomposition or Cholesky factorization. An upper limit r2 is defined to constrain the search range, such that
                          R        ⁡                  (                      s            -                                          s                ~                            ZF                                )                            2    =                    ∑                  m          =          1                M            ⁢                        r                      m            ,            m                    2                ⁢                                                                        (                                                      s                    m                                    -                                                            s                      ~                                                              zf                      ,                      m                                                                      )                            +                                                ∑                                      j                    =                                          m                      +                      1                                                        M                                ⁢                                                                            r                                              m                        ,                        j                                                                                    r                                              m                        ,                        m                                                                              ⁢                                      (                                                                  s                        j                                            -                                                                        s                          ~                                                                          zf                          ,                          j                                                                                      )                                                                                            2                      ≤                  r        2            .      As the equivalent formula of ∥R(s−{tilde over (s)}ZF)∥2 shown, the Euclidean distance (ED) is composed of M Euclidean distance increments (EDI)
                                      e          m                            2        ,    where                                        e          m                            2        =                  r                  m          ,          m                2            ⁢                                                                              (                                                      s                    m                                    -                                                            s                      ~                                                              zf                      ,                      m                                                                      )                            +                                                ∑                                      j                    =                                          m                      +                      1                                                        M                                ⁢                                                                            r                                              m                        ,                        j                                                                                    r                                              m                        ,                        m                                                                              ⁢                                      (                                                                  s                        j                                            -                                                                        s                          ~                                                                          zf                          ,                          j                                                                                      )                                                                                            2                .            The partial Euclidean distance (PED) of m-th layer is defined and represented as:
                                             d            m                    =                    ⁢                                    ∑                              i                =                m                            M                        ⁢                                          r                                  i                  ,                  i                                2                            ⁢                                                                                                            (                                                                        s                          i                                                -                                                                              s                            ~                                                                                zf                            ,                            i                                                                                              )                                        +                                                                  ∑                                                  j                          =                                                      i                            +                            1                                                                          M                                            ⁢                                                                                                    r                                                          i                              ,                              j                                                                                                            r                                                          i                              ,                              i                                                                                                      ⁢                                                  (                                                                                    s                              j                                                        -                                                                                          s                                ~                                                                                            zf                                ,                                j                                                                                                              )                                                                                                                                      2                                                                                  =                    ⁢                                    d                              m                +                1                                      +                                                                                                  e                    m                                                                    2                            .                                          
The dm merely associates with [sm, sm+1, . . . , sM] and the SD search process can thus be converted to a recursive tree search structure, as shown in FIG. 3. Additionally, {tilde over (s)}m|m+1 is defined based on Schnorr-Euchner (SE) enumeration and is represented as:
            s      ~              m      |              m        +        1              =      {                                                                                        s                  ~                                                  zf                  ,                  m                                            -                                                1                                      r                                          m                      ,                      m                                                                      ⁢                                  (                                                            ∑                                              j                        =                                                  m                          +                          1                                                                    M                                        ⁢                                                                  r                                                  m                          ,                          j                                                                    ⁡                                              (                                                                              s                            j                                                    -                                                                                    s                              ~                                                                                      zf                              ,                              j                                                                                                      )                                                                              )                                                      ,                                                              m              =              1                        ,            2            ,            …            ⁢                                                  ,                          (                              M                -                1                            )                                                                                                      s                ~                                            zf                ,                M                                      ,                                                m            =                          M              .                                          
When seeking the m-th layer, the SE enumeration first searches the signal node with minimum EDI: ŝm|m+1 (ŝm|m+1=slice({tilde over (s)}m|m+1)) and then proceed with the other nodes around {tilde over (s)}m|m+1 in a zigzag fashion. Thus, the enumeration guarantees that the signal node with smaller EDI can be preferentially visited, thereby accelerating the average seek speed.
As described, the traditional MLD is too complex to be implemented, and a sphere decoding (SD) method is introduced to reduce the complexity of MLD. Sphere decoding comprises depth-first search (DFS) and breadth-first search (BFS). With respect to the depth-first sphere decoding, the decoding latency varies much and may be quite long at lower SNR, which is not acceptable for real-time systems. Observing that the partial Euclidean distance (PED) in sphere decoding is increased monotonically with the search depth and the decoding efficiency depends largely on layer ordering, the invention tends to provide a modified sphere decoding method to mitigate the described defects.